package com.lsa.letcode.the49.anagrams;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class Solution {
	public List<String> anagrams(String[] strs) {
    	List<String> result = new ArrayList<String>();
    	if (strs == null || strs.length == 0) {
    		return result;
    	}
    	
    	Map<String, List<Integer>> sortedChars2Index = new HashMap<String, List<Integer>>();
    	for (int i = 0; i < strs.length; i++) {
    		char[] chars = strs[i].toCharArray();
    		Arrays.sort(chars);
			String sortedChars = new String(chars);
			List<Integer> indexes = sortedChars2Index.get(sortedChars);
			if (indexes == null) {
				indexes = new ArrayList<Integer>();
				sortedChars2Index.put(sortedChars, indexes);
			}
			indexes.add(i);
		}
    	
    	for (Entry<String, List<Integer>> e : sortedChars2Index.entrySet()) {
			List<Integer> indexes = e.getValue();
			if (indexes.size() > 1) {
				for (Integer i : indexes) {
					result.add(strs[i]);
				}
			}
		}
    	
    	return result;
    }
	
    public List<String> anagrams2(String[] strs) {
    	List<String> result = new ArrayList<String>();
    	if (strs == null || strs.length == 0) {
    		return result;
    	}
    	Pair[] pairs = new Pair[strs.length];
    	for (int i = 0; i < strs.length; i++) {
    		pairs[i] = new Pair(strs[i]);
		}
    	Arrays.sort(pairs, new Comparator<Pair>() {
			@Override
			public int compare(Pair p1, Pair p2) {
				return p1.sorted.compareTo(p2.sorted);
			}
		});
    	
    	boolean isPrevAdded = false;
    	for (int i = 1; i < pairs.length; i++) {
			Pair prev = pairs[i - 1];
			Pair cur = pairs[i];
			if (prev.sorted.length() == cur.sorted.length()
					&& prev.sortedHash == cur.sortedHash && prev.sorted.equals(cur.sorted)) {
				if (!isPrevAdded) {
					result.add(prev.original);
					isPrevAdded = true;
				}
				result.add(cur.original);
			}
			else {
				isPrevAdded = false;
			}
		}
    	
        return result;
    }
    
    static class Pair{
    	String original;
    	String sorted;
    	int sortedHash;
    	
		public Pair(String original) {
			this.original = original;
			char[] val = original.toCharArray();
			Arrays.sort(val);
			this.sorted = new String(val);
			this.sortedHash = sorted.hashCode();
		}
    }
}